package edu.siu.math.egut.util;

import java.io.Serializable;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.WeakHashMap;
import java.util.Map.Entry;

import org.apache.commons.collections15.list.TreeList;

import edu.siu.math.egut.io.Constants;
import edu.siu.math.egut.main.OutputStyle;

import sun.tools.tree.ThisExpression;



/**
 * An object of the Class Polynomial is a representation of a multivariate
 * Laurent polynomial with integer coefficients. For our purposes:
 * 
 * a Polynomial is a finite formal sum of "terms."
 * each "term" has a "coefficient" and a "monomial.
 * each "coefficient" is an integer.
 * each Monomial is a finite formal product of integral powers of variables.
 * (The fact that these integral powers are permitted to be negative
 * is what makes these "Laurent" polynomials.)
 * 
 * Monomials are represented by the class Monomial.
 * 
 * This class uses a store of polynomials so
 * that there is at most one of each polynomial at a time. This should reduce
 * the amount of memory used in large scale applications. 
 *
 * This class is heavily based on a similar class written in C++ by Joseph Hundley.
 * 
 * This class was written by Joe Pleso  in 2008-09.  Since then it has been 
 * adapted by Joe Hundley.
 * 
 * 
 * @author Joe Pleso
 * @author Joseph Hundley
 * 
 */
public final class Polynomial implements Serializable {
 
    private static final long serialVersionUID = 134L;
    
    /*
     * The "store" or "registry" of known polynomials.
     */
    private static final Map<Polynomial, Object> polynomials = new WeakHashMap<Polynomial, Object>();
    
    /**
     * Creates a polynomial with only a constant term.
     * 
     * @param constant an integer
     * @return the Polynomial object representing the corresponding constant polynomial.
     */
    
    /* In this implementation, a Polynomial is modeled as a Map containing Monomials and Integers.
     * The Monomials are "Keys" while the Integers are "Values."
     * If m is a key, then its value is the coefficient of that monomial in the polynomial.
     * (see "v" below.)
     */
    public static Polynomial create(Integer constant) {
	// create a map
	Map<Monomial, Integer> t = new HashMap<Monomial, Integer>();
	
	/* To clarify the next bit, let us point out that the constant polynomial 
	 * zero does not have one term with coefficient zero.  Rather it has no terms (is the empty sum).
	 */
	if (constant != 0) // so if our constant is not zero,
	    t.put(Monomial.create(new HashMap<String, Integer>()),  constant); /* we add one term, with the trivial Monomial as its 
	    								* monomial, and the given integer constant for a coefficient.
	     								*/
	// while if our constant was 0, then we do not add any terms to our map.
	
	/* Now, we check through the store.  If a Polynomial with the desired underlying data 
	 * already exists in the store, we 
	 * return that.
	 */
	for (Polynomial p : polynomials.keySet()) {
	    if (p.terms.equals(t))
		return p;
	}
	// and otherwise we call the constructor (which will also add the newly created Polynomial to the store).
	return new Polynomial(t);
    }

    /**
     * Creates a polynomial that has only has one term.
     * 
     * @param coefficient the desired integral coefficient
     * @param mono  the desired monomial 
     * @return a polynomial that has only the specified term coefficient * mono.
     */
    public static Polynomial create(Integer coefficient, Monomial mono) {
	
	// create a map.
	Map<Monomial, Integer> t = new HashMap<Monomial, Integer>();
	
	// if the coefficient is zero, then the desired Polynomial is the zero Polynomial,
	// regardless of the Monomial. If this is not the case
	if (coefficient != 0)
	    t.put(mono, coefficient); // add the pair with the desired data to the map
	// check the store, and 
	for (Polynomial p : polynomials.keySet())
	    if (p.terms.equals(t))
		return p;
	//if need be, call the Constructor.
	return new Polynomial(t);

    }

    /**
     * Default way to create a polynomial. Takes a map with monomials and the
     * corresponding coefficients. Returns the specified polynomial.
     * 
     * @param arg  the map containing the monomials and their coefficients
     * @return the polynomial containing the specified monomials and
     *         coefficients
     */
   public static Polynomial create(Map<Monomial, Integer> arg) {
	
	// check the store, to see whether there is already a Polynomial with the desired underlying data
	for (Polynomial p : polynomials.keySet())
	    if (p.terms.equals(arg))
		return p;// if so, return that
	// if not, call the Constructor
	return new Polynomial(arg);
    }
  
    /**
     * Create the polynomial that consists of a single variable.
     * @param s  String, treated as a variable 
     * @return the Polynomial equal to 1 * s ^ 1
     */
    public static Polynomial create(String s) {

	SortedMap<String, Integer> preMonomial = new TreeMap<String, Integer>();
	// Map used to construct monomial

	preMonomial.put(s.intern(), 1);
	Monomial r = Monomial.create(preMonomial);
	return create(1, r);

    }

    /**
     * Tries to parse a string into a polynomial,
     * interpreting +, -, * and ^ as algebraic operations. 
     * Sequences of digits which begin the string or 
     * follow an algebraic operator are interpreted 
     * as numbers.  
     * 
     * Parentheses, brackets, or braces  can be used to enclose exponents. 
     * Brackets or braces may be used in variables (e.g., to indicate subscripts).
     * Other use of these characters may cause confusion or exceptions. 
     * Notably, (x+y)*(x-y) will NOT be read correctly.  
     * 
     * Whitespace which is adjacent to +,-,*,^, parentheses, or left brackets and 
     * braces, or to the left of a right bracket or brace will be removed.
     * Other whitespace will be interpreted as *.
     * 
     * An exception will result from input containing / or \
     * 
     * Coefficients should always precede monomials.  For example 2*x 
     * will be read correctly, by x*2 will not.
     * 
     * @param s A string
     *                
     * @return a polynomial interpretation of s.
     * @throws PolynomialReadException if the string s can not be parsed.
     *  
     */
    
     public static Polynomial read(String s) throws PolynomialReadException  {

	 
	 
	 /* The main algorithm is to split off terms, with the division between terms being 
	  * indicated by a "+" or a "-".  Then process each term (details below), 
	  * and then add them together.
	  */
	 s = s.trim();// remove trailing/leading whitespace
	 
	 
	 Polynomial p = create(0);//initialize result as the  zero polynomial (empty sum).
	 
	 while (!(s.length()==0)){ //do this until we run out of string
	 
	      //remove trailing/leading whitespace
	     s = s.trim();
	     

	     /*Step 1:  split off the last term of the polynomial as a substring.  This task 
	      * is complicated by the fact that our Polynomials are Laurent Polynomials with
	      * negative exponents allowed.  Every "+" is indicated as separating two terms.
	      * In addition, a "-" separates two terms unless it appears in one of the 
	      * following contexts: "^-", "^(-", "^[-" or "^{-" "_-", "_(-", "_[-" or "_{-".
	      * Of course, we would want any whitespace to be ignored in making this determination. 
	      */
	     
	     // remove whitespace that might muddy the water.
	     s= s.replaceAll("\\s*\\^\\s*", "\\^").replaceAll("\\s*_\\s*", "_").replaceAll("\\s*\\-\\s*", "\\-");
	     
	     String rest=s;
	     String term = "";
	     boolean done = false;
	     int breakPoint;
	     while( !done){
		 breakPoint = Math.max(Math.max(0,rest.lastIndexOf("+")), rest.lastIndexOf("-"));
		 rest = s.substring(0,breakPoint);
		 term = s.substring(breakPoint);
		 done = !(rest.endsWith("^")||rest.endsWith(
		    "^(")
		    ||rest.endsWith("^[")
		    ||rest.endsWith("^{")||rest.endsWith("_")||rest.endsWith(
		    "_(")
		    ||rest.endsWith("_[")
		    ||rest.endsWith("_{"));
	     }
	     
	     s=rest;
	     term = term.trim();
	      //remove trailing whitespace
	     
	     boolean isNegative = term.charAt(0) == '-';
	     //get the sign of the term
	     
	     if (term.charAt(0) == '+'
	 
	     || term.charAt(0) == '-')
		 term = (term.substring(1)).trim(); //strip sign off if necessary
	     
	     
	   //find the end of the coefficient
	     int i = 0;
	     for (; i < term.length(); i++){
		 if (!Character.isDigit(term.charAt(i)))
		     break;
	     }
	     
	     int coeff;
	     if (i == 0){
		 coeff = 1;
	     }else{
		coeff  = Integer.parseInt(term.substring(0, i)); 
	     }
	      
	     term = (term.substring(i)).trim();//what's left is the monomial
	     
	     
	     try {
		if (isNegative)

		    p = p.minus(create(coeff, Monomial.read(term)));

		else
		    p = p.plus(create(coeff, Monomial.read(term)));
	     } catch (MonomialReadException e) {
		    throw new PolynomialReadException(e);
		    
		}
	   
	 }
	 return p;

    }
     
     
    /* Here is the heart of an object of Class Polynomial: a sorted Map containing 
     * Monomial keys and Integer values.
     */
    private final SortedMap<Monomial, Integer> terms;
    
    
    // The Constructor. 
    private Polynomial(Map<Monomial, Integer> arg) {
	
	
	
	/* The first step is to validate the data by checking that there are no 
	 * zero coefficients.
	 * In human communication, it's fine to write x^2+1 as x^2+0x+1, for example.
	 * For our purposes here, though, it's important that a Polynomial uniquely 
	 * determine its underlying data... and so zero terms are not permissible.
	 */
	for (Integer i : arg.values())
	    if (i == 0)
		throw new IllegalArgumentException();
	
	// with the validation complete, we simply set "terms" equal to the desired underlying data.
	terms = new TreeMap<Monomial, Integer>();
	
	
	for( Entry<Monomial, Integer> entry: arg.entrySet())
	    terms.put(entry.getKey(), entry.getValue());
	    
	// and add our new polynomial to the store.
	polynomials.put(this, null);
    }
    // The Constructor. 
    private Polynomial(Map<Monomial, Integer> arg, boolean verbose) {
	
	System.out.println("Verbose constructor:");

	if(verbose){
	    System.out.print("passed "+ arg.size() + "terms:");
	    for(Entry<Monomial, Integer> entry: arg.entrySet())
		System.out.print(entry.getValue()+ entry.getKey().toString()+",  ");
	    System.out.println();
	}

	
	
	
	/* The first step is to validate the data by checking that there are no 
	 * zero coefficients.
	 * In human communication, it's fine to write x^2+1 as x^2+0x+1, for example.
	 * For our purposes here, though, it's important that a Polynomial uniquely 
	 * determine its underlying data... and so zero terms are not permissible.
	 */
	for (Integer i : arg.values())
	    if (i == 0)
		throw new IllegalArgumentException();
	
	// with the validation complete, we simply set "terms" equal to the desired underlying data.
	terms = new TreeMap<Monomial, Integer>();

	for(Entry<Monomial, Integer> entry: arg.entrySet()){
	    System.out.println("adding entry" + 
		    entry.getValue()+
		    entry.getKey().toString());
	    System.out.print("Before: ");
	    for(Entry<Monomial, Integer> entry1: terms.entrySet())
		System.out.print(entry1.getValue()+ entry1.getKey().toString()+",  ");
	    System.out.println();
	    
	    for( Entry<Monomial, Integer> entry1: terms.entrySet())
		System.out.println(entry.getKey().toString()+" compareTo "
			+entry1.getKey().toString()+" "+ 
			entry.getKey().verboseCompareTo(entry1.getKey()));
	    terms.put(entry.getKey(), entry.getValue());
	    
	    System.out.print("Before: ");
	    for(Entry<Monomial, Integer> entry1: terms.entrySet())
		System.out.print(entry1.getValue()+ entry1.getKey().toString()+",  ");
	    System.out.println();

	}

	
	if(verbose){
	    System.out.print("have "+ terms.size() + "terms:");
	    for(Entry<Monomial, Integer> entry: terms.entrySet())
		System.out.print(entry.getValue()+ entry.getKey().toString()+",  ");
	    System.out.println();
	    System.gc();
	    System.out.print("argument passed now has "+ arg.size() + "terms:");
	    for(Entry<Monomial, Integer> entry: arg.entrySet())
		System.out.print(entry.getValue()+ entry.getKey().toString()+",  ");
	    System.out.println();

	    
	}


	
	
	// and add our new polynomial to the store.
	polynomials.put(this, null);
    }

    /*
     * THIS IS A DEFUNCT METHOD for computing the quotient in Polynomial
     * long division by a variable.  (It was rendered a bit nonsensical
     * by the shift to Laurent Polynomials.)
     * ---------------------------------------
     * This method computes the quotient when the polynomial is divided by
     * a variable (and ignores any remainder). That is the
     * result is the sum of each monomial in this polynomial that is not
     * independent of the named variable after it has been factored out.
     * 
     * @param name the name of the variable to be factored out
     * 
     * @return the polynomial q such that this polynomial is equal to 
     *  q*(name)+r.
     *  
     *  NOTE:  this method does NOT check whether or not the remainder r is 
     *  zero.
     */
     
 /*   public Polynomial quotient(String name) {
	Map<Monomial, Integer> answer = new HashMap<Monomial, Integer>();
	for (Map.Entry<Monomial, Integer> i : terms.entrySet())
	    if (!(i.getKey().getExponent(name) == 0))
		try {
		    answer.put(i.getKey().factorOut(name), i.getValue());
		} catch (MonomialVariableMissingException e) {

		    e.printStackTrace();
		    throw new RuntimeException("this shouldn't happen");
		}

	return create(answer);
  */
    /* THIS IS A DEFUNCT METHOD for computing the remainder in 
     * Polynomial long division.  It was rendered a bit nonsensical 
     * by the shift to Laurent Polynomials.
     * If p is a Polynomial, the p.remainder("x") is the remainder when p is divided by x.  That is 
     * 
     * p = q*x + p.remainder("x").  
     * 
     * @param var String, treated as variable.
     * @return the polynomial r satisfying (this) = q*var + r.  
     */
 /*   public Polynomial remainder(String var){
	Map< Monomial, Integer> answer = new HashMap<Monomial, Integer>();
	for( Map.Entry<Monomial, Integer>i: terms.entrySet())
	    if( i.getKey().getExponent(var)== 0)
		answer.put( i.getKey(), i.getValue());
	return create(answer);
    }
    */
    /**
     * Gets the number of terms in this polynomial.
     * 
     * @return the number of terms in this polynomial
     */
    public int getNumberOfTerms() {
	return terms.size();
    }

    /**
     * If p is a Polynomial, then p.degreeIn("x") is the highest positive power of x which appears in
     * p, or zero if no positive power of x appears in p.
     * 
     * @param s String, interpreted as a variable
     * @return 0 if the String does not appear, or the highest power of the string which does appear.
     */
    public int degreeIn(String s){
	int answer = 0;
	for(Monomial m: terms.keySet())
	    answer = Math.max(answer, m.degreeIn(s));
	return answer;
	    
    }
    
    /**
     * Returns the set of terms in the polynomial.
     * 
     * @return the set of terms in the polynomial
     */
    public Set<Map.Entry<Monomial, Integer>> getTerms() {
	return terms.entrySet();
    }

    /**
     * Checks if the polynomial is independent of a certain variable. This
     * implies that each composing monomial of this polynomial is independent of
     * the named variable.
     * 
     * @param name  of the variable to check
     * @return true, if the polynomial is independent of the named variable
     */
    public boolean isIndependentOf(String name) {

	for (Monomial m : terms.keySet()) {

	    if (!(m.getExponent((name)) == 0))
		return false;
	}
	return true;
    }

    /**
     * Subtracts the constant b from the polynomial a.
     * If a is a  polynomial, and b is an integer, then a.minus(b) is the polynomial a-b,
     * defined by regarding b as a constant polynomial.
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param b     the integer to be subtracted
     * @return the polynomial after subtraction has been performed
     */
    public Polynomial minus(int b) {
	return this.plus(-b);
    }

    /**
     * Subtracts a monomial from this polynomial.
     * If m is a monomial we may identify it with the Polynomial having only a single
     * term consisting of m with the coefficient 1.  
     * Then for a polynomial p, p.minus(m) indicates the Polynomial p-m.
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param m   the monomial
     * @return the difference
     */
    public Polynomial minus(Monomial m) {
	Polynomial p = this;
	return p.plus(create(-1, m));
    }
    /**
     * Interprets string argument as a polynomial consisting of a single
     * variable raised to the first power with a coefficient of 1, and subtract
     * it.  If p is a Polynomial, and s is a String, then p.minus(s) = p - 1*s^1.
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param s String, to be interpreted as the simple polynomial 1*s^1.
     * @return (this polynomial)-1*s^1
     */
    public Polynomial minus(String s) {
	Polynomial p = this;
	return p.minus(create(s));
    }

    /**
     * If a and b are Polynomials, then a.minus(b) is the Polynomial a-b.
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param b  a polynomial being subtracted.
     * @return this-b, the difference of the specified polynomials
     */
    public Polynomial minus(Polynomial b) {
	Polynomial a = this;
	return (a.plus(b.times(-1)));
    }

    /**
     * Add a constant.
     * If a is a polynomial and i is a constant then a.plus(i) is the polynomial
     * a+i, defined by regarding i as a constant polynomial.
     * 
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param i     the constant
     * 
     * @return the sum
     */
    public Polynomial plus(Integer i) {
	Polynomial p = this;
	return p.plus(create(i));
    }

    /**
     * Adds a monomial.
     * If a is a polynomial and m is a monomial then a.plus(m) is the sum a+m,
     * defined by regarding m as a polynomial with only one term consisting
     * of the monomial m with a coefficient of 1.
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param m    the monomial
     * 
     * @return the sum
     */
    public Polynomial plus(Monomial m) {
	Polynomial p = this;
	return p.plus(create(1, m));

    }
    /** 
     * Interprets its String argument s as the Polynomial 1*s^1, and 
     * adds it.  If p is a Polynomial and s is a String, then 
     * p.plus(s) = p + 1*s^1.
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param s String, to be interpreted as simple Polynomial 1*s^1
     * @return the sum of the polynomial that 
     * calls it and the simple Polynomial 1*s^1
     */
    public Polynomial plus(String s) {
	Polynomial p = this;
	return p.plus(create(s));

    }

    /**
     * Adds the two polynomials together. 
     * If a and b are polynomials, then a.plus(b) is the usual polynomial sum a+b.
     * 
     * This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * @param b    the polynomial to be added
     * 
     * @return the sum of the two polynomials
     */
    public Polynomial plus(final Polynomial b) {

	Polynomial a = this;
	if (a.terms.isEmpty() || b.terms.isEmpty())
	    return a.terms.isEmpty() ? b : a;

	Map<Monomial, Integer> p = new HashMap<Monomial, Integer>(a.terms);
	for (Map.Entry<Monomial, Integer> entry : b.terms.entrySet()) {

	    if (!p.containsKey(entry.getKey()))
		p.put(entry.getKey(), entry.getValue());
	    else {
		Integer newCoefficient = entry.getValue()
			+ p.get(entry.getKey());
		if (newCoefficient == 0)
		    p.remove(entry.getKey());
		else
		    p.put(entry.getKey(), newCoefficient);
	    }
	}
	if(p.size() != create(p).getNumberOfTerms()){
	    System.out.println("unrecoverable error adding " + this.toString() 
		    +" and "+ b.toString()+ ":\n get " + p.size() + " terms in the map.  "); 
		    Polynomial q = create(p);
		    System.gc();
		    System.out.println("Polynomial created is " + q.toString() + " with "
			    + q.getNumberOfTerms() + " terms.  After gc, original map has "
		    + p.size() + " terms.");
		    int totalCount = 0;
		    int missingCount = 0;
		    for( Entry<Monomial, Integer> entry: p.entrySet()){
			totalCount++;
			if(q.terms.containsKey(entry.getKey())){
			    System.out.println(entry.getKey() + 
				    " appears with value "+ q.terms.get(entry.getKey()));
			}else{
			    System.out.println(entry.getValue()+"" +
			    		" "+ entry.getKey().toString()+ 
			    		" appears to be missing");
			    missingCount++;
			}
		    }
		    System.out.println("counted "+ totalCount + " terms.  "+missingCount+" missing.");
		    totalCount = 0;
		    for( Entry<Monomial, Integer> entry: q.terms.entrySet()){
			totalCount++;
			System.out.println("Entry "+ totalCount +":  " +
					"" + entry.getValue()+ entry.getKey().toString());
		    }
	    System.exit(1);
	}

	return create(p);
    }

    /**
     * Raises a polynomial to a certain power. The result is returned in a new
     * polynomial. This will throw an IllegalArgumentException if power is less
     * than zero.
     * 
     * 
     * 
     * @param power   the power to raise this polynomial to
     * 
     * @return a new polynomial which contains the result of this polynomial
     *         raised to the specified power
     */
    public Polynomial raiseTo(int power) {

	Polynomial p = this;

	if (power == 1)
	    return p;
	if (power == 0)
	    return Polynomial.create(1);
	if (power < 0){
	    if(p.isASignedMonomial()){
		Monomial m = p.terms.firstKey().raiseTo(power);
		int c = (power %2 == 0)?1:p.terms.get(p.terms.firstKey());
		return Polynomial.create(c, m);
		
	    }
	     
		throw new IllegalArgumentException();
	}
	Polynomial result = p;
	for (power--; power > 0; power--) {
	    result = result.times(p);
	}
	return result;
    }

    /*
     * Remove one term from a given polynomial,
     * return a new Polynomial with one fewer terms.
     * 
     */
    private Polynomial remove(Monomial m) {

	Polynomial p = this;

	Map<Monomial, Integer> t = new HashMap<Monomial, Integer>(p.terms);
	t.remove(m);
	return create(t);
	// Remark: if m is not in the keyset for p to begin with, then p.remove(m) == p.
    }

    /**
     * This method replaces all instances of a variable with a polynomial. The
     * result is stored in a new polynomial, and neither this nor the replacement
     * polynomial is modified.
     * 
     * @param varName the variable to be replaced
     * @param replacement the polynomial that will replace the variable
     * @return the polynomial where the replacement has occurred
     * @throws BadSubstitutionException if varName appears with a negative exponent and replacement is not a signed monomial
     * 
     */
    public Polynomial replace(final String varName, final Polynomial replacement) throws BadSubstitutionException {
	
	Polynomial newPolynomial = this;
	
	// start with the zero polynomial
	Polynomial newPart = Polynomial.create(0);
	
	
	// for each term in the given polynomial
	for (Map.Entry<Monomial, Integer> entry : terms.entrySet()) {
	    
	    
	    // check whether the variable we're substituting is even there.
	    if (!(entry.getKey().getExponent(varName) == 0)) {
		if(entry.getKey().getExponent(varName) < 0 
			&& !replacement.isASignedMonomial())
		    throw new BadSubstitutionException();
	
		
		// if it is, 
		
		newPolynomial = newPolynomial.remove(entry.getKey());
		
		//we will add
		newPart = newPart.plus(
			
			//  (replacement polynomial) ^ exponent * rest of the monomial * coefficient 
		(replacement.raiseTo(entry.getKey().getExponent(varName))
			.times(

			entry.getKey().remove(varName))) // rest of the monomial... the monomial with the substituted variable removed.
			.times(entry.getValue()));// entry.getValue = coefficient of the monomial entry...
		
		
	    }
	    
	}

	return newPart.plus(newPolynomial);
    }
    
    /**
     * Returns the absolute degree of the polynomial.  (Maximum of the absolute degrees of its monomial terms.)
     * The zero Polynomial is taken to have absolute degree zero.
     * @return int equal to the degree of the polynomial.
     */
    public int getAbsoluteDegree(){
	return terms.isEmpty()?0:terms.lastKey().getAbsoluteDegree();// order on terms ensures that last is maximal absolute degree.
    }
    /**
     * Returns the degree of the polynomial.  (Maximum of the degrees of its monomial terms.)
     *The zero Polynomial is taken to have degree zero.
     * @return int equal to the degree of the polynomial.
     */
     public int getDegree(){
	 if( terms.isEmpty())
	     return 0;
	 
	int answer = terms.lastKey().getDegree();
	for(Monomial m : terms.keySet()){
	    answer =Math.max(answer, m.getDegree());
	}
	return answer;
   }
    
    /**
     * Returns a variable (String) which appears in the Polynomial, or null if the Polynomial is constant.
     * @return String a variable which appears in the polynomial
     */
    public String getVar(){
	return terms.lastKey().getVar();
    }
    
    /**
     * Creates Polynomial corresponding to the given monomial (with coefficient 1).
     * 
     * @param m monomial
     * @return m, regarded as a polynomial with coefficient 1.
     */
    public static Polynomial create(Monomial m) {
	return create(1,m);
   }

    /**
     * Multiply a polynomial by a scalar. 
     * If p is a polynomial and c is an integer, then 
     * p.times(c) is the polynomial c*p.
     * 
     * The result is returned, and the
     * polynomial is unaltered.
     * 
     * @param scalar an integer constant
     * 
     * @return the product
     */
    public Polynomial times(int scalar) {

	Polynomial poly = this;
	
	// if p=0, then c*p = p (and returning p is more efficient then calling create(0). )
	if (poly.terms.isEmpty())
	    return this;
	
	// otherwise create a map, and 
	Map<Monomial, Integer> result = new HashMap<Monomial, Integer>();
	
	// if the scalar is not zero put the desired terms in it.
	if (scalar != 0)
	    for (Map.Entry<Monomial, Integer> entry : poly.terms.entrySet()) {
		result.put(entry.getKey(), entry.getValue() * scalar);
	    }
	// if the scalar was zero, the map is empty, as it should be, since the correct
	// result is the zero polynomial, which is the "empty sum."
	return create(result);
    }

    /**
     * Multiply this polynomial by a monomial.
     * If p is a polynomial and b is a monomial, then p.times(b) is the product p*b, 
     * defined by regarding b as a polynomial with 1 term (and the implied coefficient 1.)
     * 
     * The value returned is a new polynomial.  The original polynomial is unaltered.
     * 
     * @param b     the monomial to be multiplied
     * @return the product
     */
    public Polynomial times(Monomial b) {

	Polynomial a = this;
	// If a = empty Polynomial or b = empty Monomial, then the answer is a.
	if (a.terms.isEmpty())
	    return a;
	if (b.getSize() == 0)
	    return a;

	Map<Monomial, Integer> t = new HashMap<Monomial, Integer>();

	for (Map.Entry<Monomial, Integer> eB : a.terms.entrySet()) {
	    t.put(b.multiply(eB.getKey()), eB.getValue());

	}
	return create(t);
    }
    /**
     * Interprets its string argument as a simple polynomial consisting of a single
     * variable raised to the first power, and multiplies by that polynomial.
     * If p is a polynomial and s a String, then 
     * p.times(s) = p*s
     * 
     *Examples:  if p = x y and s = "x", then p.times(s) = x^2 y.
     *If p = x+1 and s = "x+1" then p.times(s) is NOT x^2-1, because "x+1" will be interpreted not
     *as the sum of the variable x and the number 1, but as a single variable with a confusing name.
     *
     * The value returned is a new polynomial, the original polynomial is unaltered.
     * @param s a String, treated as the name of a variable
     * @return the product (this)*s^1.
     */
    public Polynomial times(final String s) {
	return this.times(create(s));

    }

    /**
     * Multiply two polynomials. The result is stored in a new polynomial, and
     * the arguments are untouched.
     * 
     * If a and b are polynomials, then a.times(b) is the product a*b.  It is,
     * of course, equal to b.times(a).
     * 
     * @param b    the other factor
     * 
     * @return the polynomial that is the product of the two factors
     */
    public Polynomial times( final Polynomial b) {

	final Polynomial a = this;
	
	/* If either a or b is the zero polynomial (as indicated by an empty set
	 * of terms), then a*b is also zero.
	 */
	if (a.terms.isEmpty() || b.terms.isEmpty())
	    return a.terms.isEmpty() ? a : b;
	
	/* otherwise the product is the sum of all the products 
	 * c*m*b, where c*m is a term of a (c an integer, m a Monomial).
	 * so we start with the zero polynomial,
	 */
	Polynomial result = Polynomial.create(0);
	
	// go through the terms of a...
	for (Map.Entry<Monomial, Integer> eA : a.terms.entrySet()) {
	    // and multiply each by b, then add the resulting polynomial to our total.
	    result = result
		    .plus((((b.times(eA.getKey())).times(eA.getValue()))));
	}
	return result;
    }

    /**
     * Returns a string representation of this polynomial.
     * 
     * 
     * @return the polynomial as a string
     */
    public String toString() {
	return toString(OutputStyle.SCREEN);
    }
    /**
     * @param sty  ignored
     * @return a String representation of the polynomial, from which the Polynomial would be 
     * recovered by Polynomial.read()
     */
    public String toMachineReadableString(final OutputStyle sty) {
	Polynomial p = this;
	if (p.terms.isEmpty())
	    return "0";

	StringBuffer sb = new StringBuffer();
	for (Map.Entry<Monomial, Integer> m : p.terms.entrySet()) {

	    if (m.getValue() >= 0)

		sb.append("+");

	    if (m.getValue() == -1)

		sb.append("-");

	    if (m.getValue() != -1 && m.getValue() != 1)

		sb.append(m.getValue());

	    if (m.getKey().getSize() != 0)

		sb.append(m.getKey().toMachineReadableString(sty));
	    if (m.getKey().getSize() == 0
		    && (m.getValue() == 1 || m.getValue() == -1))
		sb.append("1");
	}

	return sb.charAt(0) == '+' ? sb.substring(1, sb.length()) : sb
		.toString();
    }

    
    /**
     * @param sty can be TEX or SCREEN
     * @return String representation of the polynomial in the desired style
     */
    public String toString(final OutputStyle sty) {

	int maxWidth = (sty==OutputStyle.TEX)?Constants.PAGE_WIDTH:
	    ((sty==OutputStyle.SCREEN)?Constants.SCREEN_WIDTH:Integer.MAX_VALUE);
	int currentWidth =0;
	Polynomial p = this;
	if (p.terms.isEmpty())
	    return "0";

	StringBuffer sb = new StringBuffer();
	for (Map.Entry<Monomial, Integer> m : p.terms.entrySet()) {
	    if( currentWidth + 1 + m.getKey().toString(sty).length() 
		    + (int)Math.log10(Math.max(1, 
			    Math.abs(m.getValue())))
			    > maxWidth){
		if( sty == OutputStyle.TEX)
		    sb.append("\\\\");
		sb.append("\n");
	    }

	    if (m.getValue() >= 0)

		sb.append("+");

	    if (m.getValue() == -1)

		sb.append("-");

	    if (m.getValue() != -1 && m.getValue() != 1)

		sb.append(m.getValue());

	    if (m.getKey().getSize() != 0)

		sb.append(m.getKey().toString(sty));
	    if (m.getKey().getSize() == 0
		    && (m.getValue() == 1 || m.getValue() == -1))
		sb.append("1");
	}

	String s = sb.charAt(0) == '+' ? sb.substring(1, sb.length()) : sb
		.toString();
	if( sty == OutputStyle.TEX && s.contains("\\\\"))
	    return "\\begin{array}{r}" + 
	    s + "\\end{array}";
	return s;
    }
    /**
     * @param sty 
     * @param maxWidth
     * @return
     */
    public String toString(final OutputStyle sty, final int maxWidth) {

	int currentWidth =0;
	Polynomial p = this;
	if (p.terms.isEmpty())
	    return "0";

	StringBuffer sb = new StringBuffer();
	for (Map.Entry<Monomial, Integer> m : p.terms.entrySet()) {
	    if( currentWidth + 1 + m.getKey().toString(sty).length() 
		    + (int)Math.log10(Math.max(1, 
			    Math.abs(m.getValue())))
			    > maxWidth){
		if( sty == OutputStyle.TEX)
		    sb.append("\\\\");
		sb.append("\n");
		currentWidth = 0;
	    }

	    if (m.getValue() >= 0)

		sb.append("+");

	    if (m.getValue() == -1)

		sb.append("-");

	    if (m.getValue() != -1 && m.getValue() != 1)

		sb.append(m.getValue());

	    if (m.getKey().getSize() != 0)

		sb.append(m.getKey().toString(sty));
	    if (m.getKey().getSize() == 0
		    && (m.getValue() == 1 || m.getValue() == -1))
		sb.append("1");
	}

	String s = sb.charAt(0) == '+' ? sb.substring(1, sb.length()) : sb
		.toString();
	if( sty == OutputStyle.TEX && s.contains("\\\\"))
	    return "\\begin{array}{r}" + 
	    s + "\\end{array}";
	return s;
    }

    /**
     * @return true if any exponent in any monomial is negative, false if not
     */
    public boolean hasNegativeExponents() {
	for(Monomial m: terms.keySet())
	    if(m.hasNegativeExponents())
		return true;
	return false;
    }

    /**
     * Returns a list of all Strings used as variables in this Polynomial.
     * Individual Strings appear once for each Monomial in which they occur.
     * 
     * @return a List of all the Strings which are used as variables in the terms of this polynomial.
     */
    /*It might be preferable to replace this with an implementation which returns a list with 
     * each variable appearing only once.  On the other hand, at the moment this method is 
     * not called anywhere in the package, so such an improvement would be a very low priority.
     * 
     */
    public List<String> getAllVariables() {
	List<String> answer = new TreeList<String>();
	for(Monomial m: terms.keySet()){
	    answer.addAll(m.getVariables());
	    
	}
	return answer;
    }

    /**
     * p.isAVariable() is true if and only if p is a variable, i.e., has only a single term, 
     * and the monomial of that single terms has only a single variable, which is raised to 
     * the first power, and finally the coefficient of the single terms is 1.
     * 
     *  An equivalent condition is that there is a String s such that 
     * p = Polynomial.create( s ), or p.terms = [<s,1>]. 
     * 
     * 
     * @return true if the polynomial which calls it is a variable.
     */
    public boolean isAVariable() {
	return getAbsoluteDegree()==1 && getDegree()==1&& this.getNumberOfTerms()==1&&terms.containsValue(1);
    }
    

     /**
     * Ensures that all polynomials are in the store in the presence of serialization.
     * Serialization and deserialization can lead to Polynomials which exist but
     * are not "registered" in the store (not possible through the use of the Constructor
     * or create methods available to the user).  
     * 
     * This method, returns p if not it calls "create" on the underlying data of p,
     * and returns the result.
     * 
     * 
     * @param p a Polynomial
     * @return a "registered" polynomial with the same underlying data.
     */
    public static Polynomial update(Polynomial p) {
	if( polynomials.containsKey(p))
	    return p;
	else{
	    SortedMap<Monomial, Integer> t = new TreeMap<Monomial, Integer>();
	    for( Monomial m: p.terms.keySet())
		t.put(Monomial.update(m), p.terms.get(m));
	    return Polynomial.create(t);
	}
    }

    /**
     * Get the coefficient of a given monomial.
     * 
     * If p is a polynomial and m is a monomial then p.coeff(m) is the coefficient of m in p.
     * If m does not appear in p (i.e., if p can be written in such a way that m does not appear)
     * then this would be zero.
     * 
     * @param m monomial
     * @return the coefficient of m in p.
     */
    public int coeff(Monomial m) {
	return terms.get(m)== null? 0: terms.get(m);
    }

    public Polynomial coeff( String x, int i){
	
	Map<Monomial, Integer> newTerms = new HashMap<Monomial, Integer>();
	for( Entry<Monomial, Integer> e : terms.entrySet())
	    if(e.getKey().getExponent(x) == i)
		newTerms.put(e.getKey().remove(x), e.getValue());
		return create(newTerms);
    }
    
    /**
     * @param us
     * @return
     * @throws NonlinearException
     */
    public Polynomial[] coefficients(String[] us) throws NonlinearException {
	Polynomial[] answer = new Polynomial[us.length];
	for( int i = 0 ; i < us.length; i++){
	    answer[i]=Polynomial.create(0);
	    if(degreeIn(us[i])>1)
		throw new NonlinearException();
	    for( Monomial m: terms.keySet()){
		if(m.isLinearIn(us[i]))
		    answer[i]=answer[i].plus(Polynomial.create(terms.get(m),m.remove(us[i])));
		
	    }
	}
	return answer;
    
    }

    /**
     * @param string
     * @return
     */
    public boolean dependsOn(String string) {
	
	return !this.isIndependentOf(string);
    }

    /**
     * Divide every coefficient of a polynomial by an integer scalar.
     * Form a new polynomial in which the corresponding coefficient 
     * is the quotient.  (Any remainders are discarded.) 
     * 
     * The result is returned, and the
     * polynomial is unaltered.
     * 
     * @param scalar an integer constant
     * 
     * @return the quotient
     */
    public Polynomial quotientBy(int scalar) {

	Polynomial poly = this;
	if(scalar==0)
	    throw new ArithmeticException("/ by zero.");
	
	// if p=0, then p/c = p (and returning p is more efficient then calling create(0). )
	if (poly.terms.isEmpty())
	    return this;
	
	// otherwise create a map, and 
	Map<Monomial, Integer> result = new HashMap<Monomial, Integer>();
	
	// if the scalar is not zero put the desired terms in it.
	if (scalar != 0)
	    for (Map.Entry<Monomial, Integer> entry : poly.terms.entrySet()) {
		result.put(entry.getKey(), entry.getValue() / scalar);
	    }
	return create(result);
    }

    /**
     * Determines whether a given polynomial consists of a single monomial with coefficient
     * either +1 or -1.  
     * @return true iff the Polynomial is a signed monomial
     */
    public boolean isASignedMonomial() {
	if(this.terms.size() ==1)
	    return ((terms.get(terms.firstKey())==1)||(terms.get(terms.firstKey())==-1));
	return false;

    }

    public static Polynomial pow(Polynomial arg, int i) {
	
	return null;
    }

    public boolean isASignedDefaultVariable() {
	if(getAbsoluteDegree()==1 && getDegree()==1&& this.getNumberOfTerms()==1){
	    if( terms.get(terms.firstKey())==1 ||  terms.get(terms.firstKey())==-1){
		if(isADefaultVariable(terms.firstKey().getVar()))
		    return true;
	    }
	}
	return false;
    }

    public static boolean isADefaultVariable(String var) {
	
	return Unipotent.DEFAULT_VARIABLE_PATTERN.matcher(var).matches();
    }

    public Integer getFirstCoefficient() {
	return terms.get(terms.firstKey());
    }

    public Polynomial old_replace(String var, String string) {
	 TreeMap<Monomial, Integer> newTerms = new TreeMap<Monomial, Integer>();
	 for( Monomial m: terms.keySet()){
	     
	     newTerms.put(m.replace(var, string), terms.get(m));
	 }
	 return Polynomial.create(newTerms);
   }
    public Polynomial replace(String var, String string) {
	 TreeMap<Monomial, Integer> newTerms = new TreeMap<Monomial, Integer>();
	 for( Monomial m: terms.keySet()){
	     
	     newTerms.put(m.new_replace(var, string), terms.get(m));
	 }
	 return Polynomial.create(newTerms);
   }

    public Polynomial coeff(String x) {
	return coeff(x,1);
    }

    public boolean isASignedVariable() {
	if(getAbsoluteDegree()==1 && getDegree()==1&& this.getNumberOfTerms()==1)
	    return terms.containsValue(1) || terms.containsValue(-1);
	return false;
	 	
    }

    public boolean isConstant() {
	return getAbsoluteDegree() == 0;
    }

    /**
     * @param x a variable
     * @return true if every term of the polynomial is of of degree 1 in the variable x.
     */
    public boolean isLinearWithConstantTermZeroIn(String x) {
	for( Entry<Monomial, Integer> e: terms.entrySet())
	    if(e.getKey().degreeIn(x)!=1)
		return false;
	return true;
    }

    /**
     * Make a number of simultaneous substitutions.
     * @param substitutions indicating an integral multiple of a new variable to be substituted for each variable
     * @return new Polynomial produced by making the given substitutions
     */
    public Polynomial substitute(final Map<String, IntegerStringPair> substitutions) {
	Map<Monomial, Integer> newTerms = new HashMap<Monomial, Integer>();
	for( Monomial m: terms.keySet()){
	    int coeff = terms.get(m);
	    Map <String, Integer> map = new HashMap<String, Integer>();
	    for( String s:m.getVariables()){
		IntegerStringPair pair = substitutions.get(s);
		if( pair != null){
		    coeff *= pair.getInteger();
		    map.put(pair.getString(), m.getExponent(s));
		}
		else 
		    map.put(s, m.getExponent(s));
	    }
	    newTerms.put(Monomial.create(map), coeff);
	}
	    
	return Polynomial.create(newTerms);
    }

 
 
 
    
   
}
